use std::fmt::Debug;
use crate::arena::Arena;

#[derive(Clone,Debug)]
struct Node<T> {
    value: T,
    next:Option<usize>,
    prev:Option<usize>
}

impl<T> Node<T> {
    fn new(value:T) ->Node<T> {
        Self {
            value,
            next:None,
            prev:None
        }
    }
}

struct Deque<T> {
    arena: Arena<Node<T>>,
    begin:Option<usize>,
    end:Option<usize>,
}

impl<T> Deque<T> {
    fn new() -> Self {
        Self {
            arena: Arena::new(),
            begin: None,
            end:None
        }
    }
    fn push_front(&mut self, value: T) {
        let new_node = self.arena.alloc(Node::new(value));
        if let Some(begin_node) = self.begin {
            self.arena.deref_mut(new_node).next = Some(begin_node);
            self.arena.deref_mut(begin_node).prev = Some(new_node);
            self.begin = Some(new_node);
        } else {
            assert!(self.end.is_none());
            self.begin = Some(new_node);
            self.end = Some(new_node);
        }
    }
    
    fn push_back(&mut self, value:T) {
        let new_node = self.arena.alloc(Node::new(value));
        if let Some(end_node) = self.end {
            self.arena.deref_mut(new_node).prev = Some(end_node);
            self.arena.deref_mut(end_node).next = Some(new_node);
            self.end = Some(new_node);
        } else {
            assert!(self.begin.is_none());
            self.begin = Some(new_node);
            self.end = Some(new_node);
        }
    }
    
    fn pop_back(&mut self) {
        if let Some(end_ref) = self.end {
            self.end = self.arena.deref(end_ref).prev;
            self.arena.dealloc(end_ref);

            if self.end.is_none() {
                self.begin = None;
            }
        }
    }
    fn pop_front(&mut self) {
        if let Some(begin_ref) = self.begin {
            self.begin = self.arena.deref(begin_ref).next;
            self.arena.dealloc(begin_ref);

            if self.begin.is_none() {
                self.end = None;
            }
        }
    }
    
}

impl <T:Clone+Debug> Deque<T> {
    fn debug_print(&self) {
        let mut iter = self.begin;
        print!("deque: [");
        while let Some(node_ref) = iter {
            print!("{:?} ", self.arena.deref(node_ref).value);
            iter = self.arena.deref(node_ref).next;
        }
        print!("]\n");
    }
}


#[cfg(test)]
mod test {
    use super::*;
    #[test]
    fn main_test() {
        let mut deque = Deque::<i32>::new();

        for i in 0..10 {
            deque.push_back(i);
        }
        deque.debug_print();

        for i in 10..20 {
            deque.push_front(i);
        }
        deque.debug_print();

        for _ in 0..20 {
            deque.pop_front();
        }
        deque.debug_print();

        for i in 0..10 {
            deque.push_back( i);
        }
        deque.debug_print();

        for i in 0..10 {
            deque.push_front(i);
        }
        deque.debug_print();

        for i in 0..10 {
            deque.push_front(i);
        }
        deque.debug_print();
    }
}
